package com.tm.biz.tree;

import java.util.HashSet;
import java.util.Set;

public class Node {
    int val;
    Node next;

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }

    public static void main(String[] args) {
        Node node5 = new Node(5, null);
        Node node4 = new Node(3, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node head = new Node(1, node2);
        node5.next = node2;
//        Boolean circle = circle(head);
        Boolean circle3 = circle3(head);
        System.out.println(circle3);
//        dp(head);
    }


    /**
     * 第一种
     */
    public static Boolean circle(Node node) {
        Node temp = node;
        Set<Node> set = new HashSet<>();
        while (temp != null) {
            if (!set.add(temp)) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    public static Boolean circle2(Node node) {
        Node slow = node;
        Node fast = node.next;
        while (fast != null && fast.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    public static Boolean circle3(Node node) {
        Node temp = node;
        while (temp != null) {
            Node curr = temp;
            Node next = temp.next;
            while (next != null) {
                if (curr == next) {
                    return true;
                }
                next = next.next;
                if(next == null){
                    return false;
                }
            }
            temp = temp.next;
        }
        return false;
    }

    /**
     * 递归遍历
     *
     * @param node
     */
    public static void dp(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.val);
        dp(node.next);
    }
}
